package org.chen.practice.hard;

/**
 * @Author chen
 * @Date 2023/7/19 20:55
 * 题目描述
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * 算法的时间复杂度应该为 O(log (m+n))
 * 示例 1：
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 */
public class MedianSortedArrays {
    public static void main(String[] args) {
        int[] nums1 = {1,3};
        int[] nums2 = {2};
        System.out.println(findMedianSortedArrays(nums1,nums2));
    }

    /**
     * 二分查找
     * O(log(min(m,n)))
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 选择较小的数组
        if(nums1.length>nums2.length){
            int[] temp = nums1;
            nums1 =nums2;
            nums2 =temp;
        }
        int m = nums1.length;
        int n = nums2.length;
        // 获取左边的元素总个数，+1是为了不单独讨论总个数奇偶性，应为java除法向下取证 5/2=2, 4/2=2
        int totalLeft = (m+n+1)/2;
        // 再较小的数组里面找到合适的分割线[0,m]
        int left = 0;
        int right =m;

        // 开始搜索,left与right重合（找到分割线）结束
        while(left<right){
            // 假设i为nums1中的分割线，i所在位置为左侧最大值,
            // 从中点开始搜索，二分查找的核心
            int i = left +(right - left +1)/2;
            // 假设j为分割线，nums2,j所在位置为右侧最小值，nums2是较长的数组
            int j = totalLeft-i;
            // 左侧最大值大于右侧最小值，搜索范围[left,i-1]
            if(nums1[i-1] > nums2[j]){
                right = i-1;
            }else{
                // 左侧小于等于右侧，搜索范围[i,right]
                left = i;
            }
        }
        // 分割线在两个数组中均为中位线（非中线）
        // nums1 分割线
        int n1d= left;
        // 减n1d的原因，分割线左右相对平衡（最多差1个元素）
        int n2d = totalLeft -n1d;
        int n1lMax = n1d == 0? Integer.MIN_VALUE : nums1[n1d-1];
        int n1rMin = n1d == m? Integer.MAX_VALUE : nums1[n1d];
        int n2lMax = n2d == 0? Integer.MIN_VALUE : nums2[n2d-1];
        int n2rMin = n2d == n? Integer.MAX_VALUE : nums2[n2d];

        // 总数量为偶数
        if(((m+n)%2)==1){
            return Math.max(n1lMax,n2lMax);
        }else{
            // 因为数组有序，所以直接比较左边最大值和右边最小值
            return (double) (Math.max(n1lMax,n2lMax)+Math.min(n1rMin,n2rMin))/2;
        }
    }

    /**
     * 合并两个数组，
     * 使用快速排序（无需考虑数组是否有序 ），时间复杂度nlog(n)
     * 归并排序,时间复杂度nlog(n)
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArraysByMerge(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        return 0.0;
    }
}
